
//827.最大人工岛
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int dx[]={-1,1,0,0};  
        int dy[]={0,0,-1,1};
        int n=grid.size(),m=grid[0].size(),zero=0;
        //先统计每个孤立岛屿的面积
        vector<int> area(2);   //统计每个岛屿的面积,空出两个位置使得下标一一对用

        function<int(int,int)> dfs=[&](int x,int y)
        {
            grid[x][y]=area.size();  //对岛屿进行编号
            int ret=1;
            for(int k=0;k<4;k++)
            {
                int a=x+dx[k],b=y+dy[k];
                if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1) ret+=dfs(a,b);
            }
            return ret;
        };

        for(int i=0;i<n;i++)   //统计每个岛屿的面积
            for(int j=0;j<m;j++)
                if(grid[i][j]==1)
                    area.push_back(dfs(i,j));

        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]) continue;
                int sum=1;
                unordered_set<int> have;  //记录已经统计过的岛屿
                for(int k=0;k<4;k++)
                {
                    int a=i+dx[k],b=j+dy[k];
                    if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]&&!have.count(grid[a][b])) 
                    {
                        int index=grid[a][b];
                        have.insert(index);
                        sum+=area[grid[a][b]];
                    }
                }
                ans=max(ans,sum);
            }
        }
        return ans==0?n*m:ans;
    }
};